#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        vector<vector<bool>>dp(len, vector<bool>(len, true));

        for (int i = 1; i <= len; i++) {
            for (int l = 0; l + i - 1 < len; l++) {
                int r = l + i - 1;
                if (i <= 1) {
                    dp[l][r] = true;
                    continue;
                }
                if (s[l] == s[r]) {
                    dp[l][r] = dp[l + 1][r - 1];
                }
                else {
                    dp[l][r] = false;
                }
            }
        }
        vector<int> f(len + 1, 1e9);
        for (int i = 0; i < len; i++) {
            //f[i+1]=i+1;
            if (dp[0][i]) {
                f[i + 1] = 0;
                continue;
            }
            for (int j = i; j >= 0; j--) {
                if (dp[j][i]) {
                    f[i + 1] = min(f[i + 1], f[j] + 1);
                }
            }
        }
        //cout<<dp[0][0]<<endl;
       // for(int i=1;i<=len;i++){
           // cout<<f[i]<<endl;
       // }
        return f[len];

    }
};